//题目:
// 给你一个只包含三种字符的字符串，支持的字符类型分别是 '('、')' 和 '*'。
// 请你检验这个字符串是否为有效字符串，如果是 有效 字符串返回 true 。
// 有效 字符串符合如下规则：
// 任何左括号 '(' 必须有相应的右括号 ')'。
// 任何右括号 ')' 必须有相应的左括号 '(' 。
// 左括号 '(' 必须在对应的右括号之前 ')'。
// '*' 可以被视为单个右括号 ')' ，或单个左括号 '(' ，或一个空字符串 ""。
 
// 示例 1：
// 输入：s = "()"
// 输出：true

// 示例 2：
// 输入：s = "(*)"
// 输出：true

// 示例 3：
// 输入：s = "(*))"
// 输出：true
 
// 提示：
// 1 <= s.length <= 100
// s[i] 为 '('、')' 或 '*'
#include<iostream>
#include<vector>
#include<stack>

using namespace std;
//代码
class Solution 
{
public:
    bool dfs(const string& s,int pos,int count)
    {
        if(pos==s.size()) return count==0?true:false;

        if(count<0) return false;

        if(s[pos]=='(') count++;
        if(s[pos]==')') count--;

        if(s[pos]=='*')
        {
            //1.将 * 当做 ""           2.将 * 当做 ')'         3.将 * 当做 '('
            return dfs(s,pos+1,count) || dfs(s,pos+1,count+1) || dfs(s,pos+1,count-1);
        }

        return dfs(s,pos+1,count);
    }
    bool checkValidString(string s) 
    {
        //法一：动态规划    时间：O（N^3）  空间：O（N^2） 
        // int n=s.size();
        // //1.创建dp表————dp[i][j]表示：s内[i,j]子串是否为有效括号字符串
        // vector<vector<bool>> dp(n,vector<bool>(n));
        // //2.初始化————暂无
        // //3.填表————动态转移方程
        // for(int i=n-1;i>=0;i--)
        // {
        //     if(s[i]=='*') dp[i][i]=true;
        //     for(int j=i+1;j<n;j++)
        //     {
        //         if(j==i+1 && s[i]!=')' && s[j]!='(') dp[i][j]=true;
        //         else
        //         {
        //             for(int k=i+1;k<j;k++)
        //             {
        //                 if((s[i]!=')' && s[j]!='(' && dp[i+1][j-1]) || (s[k]=='*' && dp[i][k]==true && dp[k][j]==true) || (dp[i][k]==true && dp[k+1][j]==true))
        //                 {
        //                     dp[i][j]=true;
        //                     break;
        //                 }
        //                 if((s[i]=='*' && dp[i+1][j]==true)  || (s[j]=='*' && dp[i][j-1]==true))
        //                     dp[i][j]=true;
        //             }
        //         }
        //     }
        // }
        // //4.确定返回值
        // return dp[0][n-1];

        //法二：递归   超时————×
        // return dfs(s,0,0);

        //法三：栈
        stack<int> st,star_st;//创建两个栈，一个存左括号，一个存*
        for(int i=0;i<s.size();i++)
        {
            char c=s[i];
            if(c=='(') st.push(i);
            if(c==')') 
            {
                if(st.empty()!=true) st.pop();
                else if(star_st.empty()!=true) star_st.pop();
                else return false;
            }
            if(c=='*') star_st.push(i);
        }
        while(!st.empty() && !star_st.empty())
        {
            int right=star_st.top();star_st.pop();
            int left=st.top();st.pop();
            if(left>right) return false;
        }
        return st.empty();
    }
};